//
//  Problem167.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 167. 两数之和 II - 输入有序数组
 给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

 示例 1：
     输入：numbers = [2,7,11,15], target = 9
     输出：[1,2]
     解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 示例 2：
     输入：numbers = [2,3,4], target = 6
     输出：[1,3]
 示例 3：
     输入：numbers = [-1,0], target = -1
     输出：[1,2]
 提示：
     2 <= numbers.length <= 3 * 104
     -1000 <= numbers[i] <= 1000
     numbers 按 递增顺序 排列
     -1000 <= target <= 1000
     仅存在一个有效答案
 */
@objcMembers class Problem167: NSObject {
    func solution() {
        print(twoSumPoint([2,7,11,15], 9))
        print(twoSumPoint([2,3,4], 6))
        print(twoSumPoint([-1,0], -1))
    }
    
    /*
     二分法：
     依次遍历数组，例如 i=0 numbers[0]=2,然后通过二分法查找 [1...n-1]查找target-2的位置
     */
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        for i in 0..<numbers.count {
            if numbers[i] > target {
                break
            }
            
            var l = i + 1
            var r = numbers.count-1
            var mid = 0
            while l <= r {
                mid = l + (r - l) >> 1
                print(mid, l , r)
                if numbers[mid] == target - numbers[i] {
                    return [i+1, mid+1]
                } else if numbers[mid] > target - numbers[i] {
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            }
            
        }
        return [-1, -1]
    }
 
    /*
     双指针：
     1: 创建2个指针i，j，分别指向开始和结束
     2: 计算numbers[i] + numbers[j] 与 target 大小的比较
     3: 如果 > target，那么j--， == target，找到，< target i++
     */
    func twoSumPoint(_ numbers: [Int], _ target: Int) -> [Int] {
        var start = 0
        var end = numbers.count - 1
        while start < end {
            if numbers[start] + numbers[end] == target {
                return [start+1, end+1]
            } else if numbers[start] + numbers[end] > target {
                end -= 1
            } else {
                start += 1
            }
        }
        return [-1, -1]
    }
}
